package HOT;

/**
 * Author  zxy
 * Date  2023/7/15 09:21
 */

/*
* 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
* 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
* 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
* */

public class LengthOfLIS_300 {
    public int lengthOfLIS(int[] nums) {

        // 二分查找
        int n = nums.length;

        int[] arrs = new int[n];
        arrs[0] = nums[0];
        int len = 0;

        for (int i = 1; i < n; i++) {
            if (nums[i] > arrs[len]) {
                arrs[++len] = nums[i];
            } else {
                int left = 0;
                int right = len;
                int pos = -1;

                while (left <= right) {
                    int mid = (left + right) >> 1;

                    if (nums[i] > arrs[mid]) {
                        left = mid + 1;
                        pos = mid;
                    } else if (nums[i] < arrs[mid]) {
                        right = mid - 1;
                    } else {
                        pos = mid - 1;
                        break;
                    }
                }

                arrs[pos + 1] = nums[i];
            }

            // System.out.println(Arrays.toString(arrs));
        }

        return len + 1;

        // dp
        /*
        int len = nums.length;

        int[] arrs = new int[len];
        Arrays.fill(arrs, 1);

        int ans = 1;

        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    arrs[i] = Math.max(arrs[i], arrs[j] + 1);
                }
            }

            ans = Math.max(ans, arrs[i]);
        }

        // System.out.println(Arrays.toString(arrs));

        return ans;
        */
    }
}
